1. Field of the Invention
This invention relates to a method and apparatus for optimizing an organization of many discrete elements. Specifically, a method and apparatus for optimizing the logic design of an integrated circuit to achieve a more simplified, less redundant, functional design capable of faster timing.
2. Description of Related Art
Computers are being employed more often to improve and enhance the organization of large scale integrated circuits. Such an organization is necessary for the resolution of a cell assignment problem of a logical functional element mask in a circuit mask layout. The cell element assignment determines a plurality of objectives, such as chip size and minimization, utilization of redundant functional elements, minimization of wire length, and enhanced circuit timing.
Logic designs follow typical design cycles. Usually, a first functional cycle is investigated. Next, a second cycle requires performance tuning and the elimination of logic defects or xe2x80x9cbugsxe2x80x9d. As a product is performance tuned, a larger number of logic paths begin converging to a timing limit, necessitating operational frequencies in the hundreds of mega Hertz for proper operation. Typically, designers spend a substantial amount of time at this stage of the design employing static analysis tools in order to acquire a map of the logic paths over a selected clock cycle. The standard approach is to find the worse offenders contributing to timing constraints within the circuit, improve on these paths, and then sequentially move on to the next set of timing offenders. The prior art approaches this by moving the signal under inspection ahead in its timing path, and replacing the underlying cone of logic or redesigning the function associated with the path to make the circuit faster. However, as the timing paths or waves are completed, the number of associated paths that need to be improved begin increasing non-linearly, analogous to the number of leaves stemming from the twigs of the branches of a tree. Eventually, the number of logic paths that need timing improvement is so large that the designers declare a xe2x80x9cperformance wallxe2x80x9d has been reached. In the current state of the art, all circuits reach their performance limit in the frequency range of a few hundred mega Hertz. If design requirements necessitate performance faster than this, other methodologies need to be employed. At this stage, the designers usually begin investigating different solutions for performance enhancements, such as technology migration. Unfortunately, the next available technology may be outside the market window for the integrated circuit (IC) under design. Another approach is do to a full-scale custom build of the IC. However, the cost of a custom build remains prohibitive, and the time to market for this type of build is further extended.
In U.S. Pat. No. 5,638,290 issued to Ginetti, et al., on Jun. 10, 1997, entitled, xe2x80x9cMETHOD FOR ELIMINATING A FALSE CRITICAL PATH IN A LOGIC CIRCUIT,xe2x80x9d a method is taught for removing the critical false paths taken place during logic optimization. This method automatically finds when a path node does not affect the behavior of the path output and so determines a false critical path. By finding a false critical path, this methodology effectively eliminates a function from the logic design. However, it fails to optimize the critical paths for timing.
In U.S. Pat. No. 5,654,898 issued to Roetcisoender, et al., on Aug. 5, 1997, entitled, xe2x80x9cTIMING-DRIVEN INTEGRATED CIRCUIT LAYOUT THROUGH DEVICE SIZING,xe2x80x9d a method for determining the layout of an IC is taught, in accordance with timing constraints, by means of sizing the buffers in the layout. Based on delay data developed from the routing of parasitics, this invention calls on module generators to build cells with the output drive strength required to meet predetermined performance goals, which frequently requires modifying the buffer sizes. The buffers are resized so that the time delays in the time-critical paths are either brought within the predetermined timing criteria, or no further improvement in any time-critical path is possible. Thus, under this method, approaching the performance wall requires the resizing of buffers until a physical limit is reached where no further improvement is possible.
Bearing in mind the problems and deficiencies of the prior art, it is therefore an object of the present invention to provide a method and apparatus to analyze and enhance the total performance of the logic design of a large scale integrated circuit.
It is another object of the present invention to provide and method and apparatus to optimize the timing of an integrated circuit design.
A further object of the invention is to provide a method and apparatus overcome the shortcomings of prior art methods of minimizing circuit timing in large scale integrated circuits.
It is yet another object of the present invention to provide a computer aided design system and method for enhancing large scale integrated circuit timing, and optimizing the circuit paths in the logic design.
Another object of the present invention is to provide a computer aided design system and method to identify precise places in a large scale integrated circuit logic design to optimize performance and timing, and to maximize the circuit performance gain.
Still other advantages of the invention will in part be obvious and will in part be apparent from the specification.
The above and other advantages, which will be apparent to one of skill in the art, are achieved in the present invention which is directed to, in a first aspect, a method of designing a logic circuit comprising the steps of: identifying functional paths in the logic circuit that include multiple elements in common with other functional paths; grouping the identified functional paths into groups having functional paths with the same elements in common; ranking the groups according to a number of elements that the functional paths in each group have in common; and, optimizing a performance of a first group of functional paths into a second group of functional paths wherein a number of common elements in the functional paths of the second group is less than a number of common elements in the functional paths of the first group.
The present invention is directed to, in a second aspect, a method of designing a logic circuit having a plurality of logic functions, and logic paths having logic path elements, comprising the steps of: running performance tests on the logic circuit; listing all of the logic paths in the logic circuit; finding the logic path elements of the logic paths that are common to one another; ranking the common logic path elements by the number of critical paths associated with each, assigning a higher ranking value to the common logic path elements with the greater number of the critical paths; collapsing the higher ranking common logic path elements to minimize propagation times of the logic circuit and eliminate redundancy in the logic functions; and, re-running the performance tests on the logic circuit.
In a third aspect, the present invention is directed to a method of designing a logic circuit having a plurality of logic functions, and logic paths having leaves, twigs, and branches as logic path elements, comprising the steps of: providing a computer processing system; generating a data structure to identify each of the logic path leaves in the logic circuit; running a performance test using the computer processing system on the logic circuit to characterize critical paths of the logic paths; cross-referencing the logic path leaves to the number of the critical paths associated with each of the logic path leaves; sorting and grouping the logic path leaves according to the number of the critical paths associated with each of the logic path leaves; and, performing a first level performance screen on the sorted and grouped logic path leaves.
Additionally, this third aspect may further comprise the steps of: cross-referencing the logic path twigs to the number of the critical paths associated with each of the logic path twigs; sorting and grouping the logic path twigs according to the number of the critical paths associated with each of the logic path twigs; customizing and optimizing common logic path twig groups to minimize propagation times of the logic circuit and eliminate redundancy in the logic functions; and, converting one or more of the common logic path twig groups into logic path leaves.
Further, this aspect may include the steps of: cross-referencing the logic path branches to the number of the critical paths associated with each of the logic path branches; sorting and grouping the logic path branches according to the number of the critical paths associated with each of the logic path branches; customizing and optimizing common logic path branch groups to minimize propagation times of the logic circuit and eliminate redundancy in the logic functions; and, converting one or more of the common logic path branch groups into logic path twigs.
The present invention is also directed to, in a fourth aspect, a program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform the method steps for designing a logic circuit having a plurality of logic functions, and logic paths having leaves, twigs, and branches as logic path elements, the method steps comprising; running performance tests on the logic circuit; listing all logic paths; finding the logic path leaves, twigs, and branches of the logic paths that are common to one another; ranking the common leaves, twigs, and branches of the logic paths by the number of critical paths associated with each, assigning a higher ranking value to the common logic path leaves, twigs, and branches with the greater number of the critical paths; collapsing the higher ranking common logic path leaves, twigs, and branches, to minimize propagation times of the logic circuit and eliminate redundancy in the logic functions; and, re-running the performance tests on the logic circuit.